import java.util.ArrayList;
import java.util.List;

public class Test_9_6 {


    //力扣：88. 合并两个有序数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while(i >= 0 && j >= 0) {
            if(nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            }else {
                nums1[k--] = nums2[j--];
            }
        }
        if(i < 0) {
            while(j >= 0) {
                nums1[k--] = nums2[j--];
            }
        }
    }


    //力扣：26. 删除有序数组中的重复项
    public int removeDuplicates(int[] nums) {
        int len = 0;
        for(int i = 0; i < nums.length; i++) {
            if(i == nums.length-1 || nums[i] != nums[i+1]) {
                nums[len++] = nums[i];
            }else {
                while(i < nums.length-1 && nums[i] == nums[i+1]) {
                    i++;
                }
                nums[len++] = nums[i];
            }
        }
        return len;
    }




    //力扣：27. 移除元素
    public int removeElement(int[] nums, int val) {
        int len = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != val) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }


    //力扣：118. 杨辉三角
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();
        for(int i = 0; i < numRows; i++) {
            List<Integer> tmp = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    tmp.add(1);
                }else {
                    tmp.add(answer.get(i - 1).get(j - 1) + answer.get(i - 1).get(j));
                }
            }
            answer.add(tmp);
        }
        return answer;
    }



    //力扣：189. 轮转数组
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int[] tmp = new int[k];
        int count = k;
        //1. 把 nums数组中后 K 个元素按顺序依次放入 tmp 数组中
        for(int i = nums.length-1; count > 0; count--,i--) {
            tmp[count-1] = nums[i];
        }
        //2. 把数组中前 len-k 个元素往后移动 k 个位置
        for(int i = nums.length-1-k; i >=0; i--) {
            nums[i+k] = nums[i];
        }
        //3. 把 tmp 数组中的元素依次放入 nums 数组中
        for(int i = 0; i < k; i++) {
            nums[i] = tmp[i];
        }
    }



    //力扣：面试题 17.04. 消失的数字
    public int missingNumber(int[] nums) {
        int[] count = new int[nums.length+1];
        for(int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
        }
        for(int i = 0; i < count.length; i++) {
            if(count[i] == 0) return i;
        }
        return -1;
    }
}
